#include "util.hpp"

//! \brief A more generic binary search using C++ templates and iterators
//! \param begin Iterator pointing to the first element
//! \param end Iterator pointing to one past the last element
//! \param key The value to be searched for
//! \return An iterator pointing to the location of the value in the given
//! vector, or one past the end if the value was not found.
template<typename Iterator, typename T>
Iterator binary_search_it(Iterator& begin, Iterator& end, boost::shared_ptr<T> key)
{
    // Keep halving the search space until we reach the end of the vector
    Iterator NotFound = end;

    while(begin < end)
    {
        // Find the median value between the iterators
        Iterator Middle = begin + (std::distance(begin, end) / 2);

        // Re-adjust the iterators based on the median value
        if(*Middle == key)
        {
            return Middle;
        }
        else if(*Middle > key)
        {
            end = Middle;
        }
        else
        {
            begin = Middle + 1;
        }
    }

    return NotFound;
}

/*template<class Iterator, class T>
void remove(Iterator& begin, Iterator& end, const T& value)
{
    std::erase(std::find_if(begin, end, value), end);
}


template<class Iterator, class T>
void remove_if(Iterator& begin, Iterator& end, bool (*compare)(int) )
{
    std::erase(std::find_if(begin, end, compare), end);
}*/
